<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
  
<!-- Mirrored from bos.asmhackers.net/docs/filesystems/ntfs/runlist.html by HTTrack Website Copier/3.x [XR&CO'2013], Tue, 07 Oct 2014 11:26:07 GMT -->
<head>
    <title>NTFS Documentation: Runlist</title>
  </head>

  <body>
      <h1><a href="index-2.html#NTFS" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/index.html#NTFS">NTFS</a> Documentation: Runlist</h1>

      <h2>Definition</h2>

      This is a table written in the <a href="attribute.html#content_part" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#content_part">content part</a> of a <a href="attribute.html#non_resident" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#non_resident">non-resident file attribute</a>, which allows to have access to its <a href="attribute.html#stream" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#stream">stream</a>.
      <p>

      <h2>Layout</h2>

      The runlist is a sequence of <a name="element">element</a>s: each element stores an offset to the starting <a href="glossary.html#LCN" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#LCN">LCN</a> of the previous element and the length in <a href="glossary.html#Cluster" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Cluster">cluster</a>s of a <a href="attribute.html#run" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#run">run</a>.
      <p>

      To save space, Offset and Length are variable size fields (probably up to 8 bytes), and an element is written in this crunched format:
      <p>

      <table border=2 cellspacing=2 cellpadding=2>
	<tr bgcolor="#E0E0E0">
	  <th>Offset <em>in <a href="glossary.html#Nibble" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Nibble">nibble</a></em> to the beginning of the element</th>
	  <th>Length</th>
          <th>Description</th>
        </tr>
        <tr>
          <th>0</th>
	  <th>1</th>
          <th>F=Size of the Offset field</th>
        </tr>
        <tr>
          <th>1</th>
	  <th>1</th>
          <th>L=Size of the Length field</th>
        </tr>
        <tr>
	  <th>2</th>
          <th>2*L</th>
          <th>Length of the run</th>
        </tr>
        <tr>
          <th>2+2*L</th>
	  <th>2*F</th>
          <th><a href="runlist.html#offset" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/runlist.html#offset">Offset to the starting LCN of the previous element</a></th>
        </tr>
      </table>
      <p>

      <dl>
	<dt><a name="offset">Offset to the starting <a href="glossary.html#LCN" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#LCN">LCN</a> of the previous <a href="runlist.html#element" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/runlist.html#element">element</a></a>
	  <dd>This is a signed value. For the first <a href="runlist.html#element" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/runlist.html#element">element</a>, consider the offset as relative to the <a href="glossary.html#LCN" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#LCN">LCN</a> 0, the beginning of the <a href="glossary.html#Volume" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Volume">volume</a>.
	  <p>

      </dl>
      <p>

      The layout of the runlist must take account of the <a href="attribute.html#compressed" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#compressed">data compression</a>: the set of <a href="attribute.html#VCN" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#VCN">VCN</a>s containing the <a href="attribute.html#stream" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#stream">stream</a> of a <a href="attribute.html#compressed" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#compressed">compressed file attribute</a> is divided in compression units (also called chunks) of 16 <a href="glossary.html#Cluster" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Cluster">cluster</a>s: <a href="attribute.html#VCN" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#VCN">VCN</a>s 0 to 15 constitutes the 1st compression unit, <a href="attribute.html#VCN" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#VCN">VCN</a>s 16 to 31 the 2nd one, and so on... For each compression unit,
      <ul>
        <li>The alpha stage of compression is very simple and is independant of the <a href="attribute.html#engine" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#engine">compression engine</a> used to compress the <a href="attribute.html" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html">file attribute</a>: if all the 16 <a href="glossary.html#Cluster" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Cluster">cluster</a>s of a compression unit are full of zeroes, this compression unit is called a sparse unit and is not physically stored. Instead, an element with no Offset field (F=0, the Offset is assumed to be 0 too) and a Length of 16 <a href="glossary.html#Cluster" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Cluster">cluster</a>s is put in the runlist.
        <p>

        <li>Else, the beta stage of compression is done by the <a href="attribute.html#engine" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html#engine">compression engine</a> used to compress the <a href="attribute.html" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/attribute.html">file attribute</a>: if the compression of the unit is possible, N (&lt; 16) <a href="glossary.html#Cluster" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Cluster">cluster</a>s are physically stored, and an element with a Length of N is put in the runlist, followed by another element with no Offset field (F=0, the Offset is assumed to be 0 too) and a Length of 16 - N.
        <p>

        <li>Else, the unit is not compressed, 16 <a href="glossary.html#Cluster" tppabs="http://www.via.ecp.fr/~regis/ntfs/new/glossary.html#Cluster">cluster</a>s are physically stored, and an element with a Length of 16 is put in the runlist.
        <p>

      </ul>

      In pratice, this is a bit more complicated because some of the element can be gathered. But let's take an ... 

      <h3>...Example</h3>
      We have to decode the following runlist:
      <pre>21 14 00 01 11 10 18 11 05 15 01 27 11 20 05</pre>

      First, we have to decrunch it. We obtain the readable format used to initialize the <b>runlist[]</b> table in the following example of C code. Second, we have to execute this program (a short code is sometimes better that long and confusing explanations):

<pre>
/* printf */
#include &lt;stdio.h&gt;

struct s_element {
    int Offset, Length;
    };

struct s_element <b>runlist[]</b> = {
    {<b>0x100</b>, <b>0x14</b>},
    {<b> 0x18</b>, <b>0x10</b>},
    {<b> 0x15</b>, <b> 0x5</b>},
    {<b>  0x0</b>, <b>0x27</b>},
    {<b>  0x5</b>, <b>0x20</b>}
    };

int main(int argc, char **argv) 
{
    int index, V, L, LRef, R, cont;
    struct s_element begin, end;
    
    index = 0;
    end = runlist[index];
    L = LRef = end.Offset;
    V = 0;
    
    do {
	R = 16 - (V%16);
	if (R == 16) {
	    printf ("Compression unit beginning at VCN %x\n", V);
	    begin = end;
	}
	if (end.Length &gt;= R) {
	    if (begin.Offset)
		if (end.Offset)
		    printf (" %x clusters at LCN %x\n"
                            " Unit not compressed\n", R, L);
		else
		    printf (" %x unused clusters: compressed unit\n",
		      R);
	    else
		printf (" 10 zeroed clusters: sparse unit\n");
	    L += R;
	    V += R;
	    end.Length -= R;
	}
	else {
	    printf (" %x clusters at LCN %x\n", end.Length, L);
	    V += end.Length;
	    end.Length = 0;
	}
	
	if (end.Length)
	    cont = 1;
	else
	    if (++index &lt; (sizeof(runlist)/sizeof(struct s_element))) {
		end = runlist[index];
		L = LRef += end.Offset;
		cont = 1;
	    }
	    else
		cont = 0;
    } while (cont);

    exit(0);
}
</pre>

      The above program finally produces the following output:
<pre>
Compression unit beginning at VCN 0
 10 clusters at LCN 100
 Unit not compressed
Compression unit beginning at VCN 10
 4 clusters at LCN 110
 c clusters at LCN 118
 Unit not compressed
Compression unit beginning at VCN 20
 4 clusters at LCN 124
 5 clusters at LCN 12d
 7 unused clusters: compressed unit
Compression unit beginning at VCN 30
 10 zeroed clusters: sparse unit
Compression unit beginning at VCN 40
 10 zeroed clusters: sparse unit
Compression unit beginning at VCN 50
 10 clusters at LCN 132
 Unit not compressed
Compression unit beginning at VCN 60
 10 clusters at LCN 142
 Unit not compressed
</pre>

      As you can see, the runlist format is really brain-damaged:)
      <p>

      <em>Note</em>: If you have a shorter code that can produce the same output, please let me know. 
      <p>

      <hr>
      <address><a href="mailto:regis@via.ecp.fr">Regis Duchesne</a> at <a href="javascript:if(confirm('http://www.via.ecp.fr/  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.via.ecp.fr/'" tppabs="http://www.via.ecp.fr/">VIA</a>, <a href="javascript:if(confirm('http://www.ecp.fr/  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.ecp.fr/'" tppabs="http://www.ecp.fr/">ECP</a>, France</address>
<!-- Created: Sun Jan 12 00:20:50 MET 1997 -->
<!-- hhmts start -->
Last modified: Sat Jan 23 20:15:14 PST 1999
<!-- hhmts end -->
  </body>

<!-- Mirrored from bos.asmhackers.net/docs/filesystems/ntfs/runlist.html by HTTrack Website Copier/3.x [XR&CO'2013], Tue, 07 Oct 2014 11:26:07 GMT -->
</html>
